#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<unordered_map>
#include<queue>
using namespace std;

int bfs(string start, string end, vector<string>& bank);

int minMutation(string startGene, string endGene, vector<string>& bank)
{
    int ret = bfs(startGene, endGene, bank);
    return ret;
}


int bfs(string start, string end, vector<string>& bank)
{
    unordered_map<string, int> hash1;
    unordered_map<string, int> hash2;
    vector<char> v = { 'A','C','G','T' };
    int count = 0;
    hash1[start]++;
    for (auto& e : bank)
    {
        hash2[e]++;
    }
    queue<string> q;
    q.push(start);
    while (q.size())
    {
        int sz = q.size();
        for (int i = 0; i < sz; i++)
        {
            string s = q.front();
            q.pop();
            int tag = 0;
            for (int m = 0; m < start.size(); m++)
            {
                for (int n = 0; n < 4; n++)
                {
                    string temp = s;
                    temp[m] = v[n];
                    if (hash2.count(temp) == 1)
                    {
                        if (hash1.count(temp) == 0)
                        {
                            hash1[temp]++;
                            q.push(temp);
                            if (tag == 0)
                            {
                                count++;
                            }
                            tag = 1;
                        }
                        if (temp == end)
                        {
                            return count;
                        }
                    }
                }
            }
        }
    }
    return -1;
}



void test1()
{
    string startGene = "AACCGGTT";
    string endGene = "AAACGGTA";
    vector<string> bank = { "AACCGGTA", "AACCGCTA", "AAACGGTA" };
    int ret=minMutation(startGene, endGene, bank);
}

void test2()
{
    string startGene = "AAAAAAAA";
    string endGene = "ACAAAAAA";
    vector<string> bank = { "CAAAAAAA", "CCAAAAAA", "ACAAAAAA" };
    int ret=minMutation(startGene, endGene, bank);
}
int main()
{
    test2();
    return 0;
}